package com.zyk.leetcode;

import java.util.Arrays;

/**
 * @author zhangsan
 * @date 2021/5/4 12:09
 */
public class C1473 {


    // houses: 当前房子的颜色, 1 ~ n
    // cost: 将第i个房子刷成  1~n 所需要的花费
    // m: 房子的个数
    // n: 颜色的种数
    // target: 连续的相同颜色为一组, 组成target组
    // 问题: 组成target组最少的花费
    public static int minCost(int[] houses, int[][] cost, int m, int n, int target) {
        if (m < target) {
            return -1;
        }
        Integer[][] dp = new Integer[m + 1][target + 1];
        int ans = process(houses, cost, m, n, 0, target, dp);
        for (Integer[] nums : dp) {
            System.out.println(Arrays.toString(nums));
        }
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }

    public static int process(int[] houses, int[][] cost, int m, int n, int i, int rest, Integer[][] dp) {
        if (dp[i][rest] != null) {
            return dp[i][rest];
        }
        int ans = Integer.MAX_VALUE;
        if (i == m) {            // 来到最后一个房子, 需要的花费
            ans = rest == 0 ? 0 : Integer.MAX_VALUE;
        } else if ((rest = i != 0 && houses[i] != houses[i - 1] ? rest - 1 : rest) < 0) {
            return Integer.MAX_VALUE;
        } else if (rest == 0) {
            if (houses[i] == houses[i - 1]) {
                ans = process(houses, cost, m, n, i + 1, rest, dp);
            } else if (houses[i] == 0) {
                int temp = houses[i];
                houses[i] = houses[i - 1];
                int next = process(houses, cost, m, n, i + 1, rest, dp);
                if (next != Integer.MAX_VALUE) {
                    ans = cost[i][houses[i - 1] - 1] + next;
                }
                houses[i] = temp;
            }
        } else {
            // 1. 我修改我自己为houses[i]~n. rest=houses[i] == houses[i-1] ? rest : rest-1;
            // 2. 当前为0 必须修改
            // 3. 只能往大的颜色修改
            if (houses[i] != 0) {
                ans = process(houses, cost, m, n, i + 1, rest, dp);
            } else {
                for (int j = 1; j <= n; j++) {  // p2 当前改变
                    if (j == 0) continue;   // 当前是0, 必须修改
                    int curCost = cost[i][j - 1];
                    int temp = houses[i];
                    houses[i] = j;
                    int nextCost = process(houses, cost, m, n, i + 1, rest, dp);
                    if (nextCost != Integer.MAX_VALUE) {
                        ans = Math.min(ans, curCost + nextCost);
                    }
                    houses[i] = temp;
                }
            }
        }
        return dp[i][rest] = ans;
    }

    // for test
    public static void main(String[] args) {
        int[] houses = {0, 0, 0, 0, 0};
        int[][] cost = {
                {1, 10}, {10, 1}, {10, 1}, {1, 10}, {5, 1}
        };
        int m = 5;
        int n = 2;
        int target = 3;
        System.out.println(minCost(houses, cost, m, n, target));
    }

}
